Teoria kratowa

Teoria kratowa (lattice theory) jest gałęzią matematyki zajmującą się badaniem struktur zwanych kratami. Kraty pojawiają się w wielu dziedzinach, m.in. w algebrze, logice, topologii, grafach oraz w informatyce.

Definicja

Kratą nazywamy niepustą strukturę uporządkowaną porządkową (P, ≤), w której każda para elementów a, b ∈ P ma zarówno supremum (najmniejszy element większy od obu, zwany join lub supremum) jak i infimum (największy element mniejszy od obu, zwany meet lub infimum). Formalnie:

istnieje element a ∨ b (join) taki, że a ≤ a ∨ b, b ≤ a ∨ b oraz dla każdego c spełniającego a ≤ c i b ≤ c zachodzi a ∨ b ≤ c;
istnieje element a ∧ b (meet) taki, że a ∧ b ≤ a, a ∧ b ≤ b oraz dla każdego d spełniającego d ≤ a i d ≤ b zachodzi d ≤ a ∧ b.

Operacje ∨ i ∧ są łączące, przemienne i absorpcyjne, co czyni kratę przykładem algebry z dwoma binarnymi operacjami.

Historia

Początki teorii kratowych sięgają pracy George'a Boole'a (1815–1864), który badał algebrę logiczną. W XIX wieku Richard Dedekind wprowadził pojęcie "lattice" w kontekście teorii ciał liczbowych. Pełny rozwój teorii przypisuje się pracom Marshalla Stone'a (1930) oraz Garrett'a Birkhoffa (1940), którzy ukonkretowali aksjomaty i zastosowania kratek w algebrze i logice.

Podstawowe pojęcia

Element maksymalny i minimalny – element m jest maksymalny, jeśli nie istnieje n ≠ m taki, że m ≤ n; analogicznie dla minimalnego.
Górny i dolny element – element największy (górny) ⊤ spełnia x ≤ ⊤ dla każdego x; dolny ⊥ spełnia ⊥ ≤ x dla każdego x.
Podkrata – podzbiór S ⊆ P zamknięty względem operacji ∨ i ∧.
Homomorfizm kratowy – funkcja f : P → Q zachowująca oba działania: f(a ∧ b) = f(a) ∧ f(b) oraz f(a ∨ b) = f(a) ∨ f(b).

Rodzaje kratek

Kraty rozproszone

Każda para elementów posiada zarówno supremum, jak i infimum, ale nie ma dodatkowych własności.

Kraty całkowite

Kratą całkowitą (ang. complete lattice) nazywamy taką, w której każdy podzbiór (nie tylko dwuelementowy) ma supremum i infimum. Przykładem jest moc zbioru 2^X z operacjami ∪ i ∩.

Kraty rozproszone (distributive)

Kratę nazywamy rozdzielną, jeśli spełnia prawa rozdzielności:
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) oraz a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c). Typowym przykładem są kraty boolowskie, czyli struktury logiki dwuwartościowej.

Kraty modularne

Kratę modularną definiuje warunek: jeśli a ≤ c, to a ∨ (b ∧ c) = (a ∨ b) ∧ c. Modułowość jest pośrednia między rozdzielnością a ogólną strukturą.

Zastosowania

Teoria kratowa ma szerokie zastosowanie w różnych dyscyplinach:

Algebra – opis struktury podgrup, ideałów i podmodulek.
Logika – modele logik intuicjonistycznych, algebraiczne semantyki oraz logika modalna.
Informatyka – analiza typów, teoria domen (domeny), systemy wersjonowania i kolejki priorytetowe.
Topologia – kraty otworów (zestaw otwartych podzbiorów przestrzeni topologicznej) są kratem całkowitym.
Fizyka – w teorii kratowej opisuje się uporządkowane stany w systemach kwantowych oraz struktury kratowe w krystalografii.

Powiązane pojęcia

Warto zapoznać się także z następującymi zagadnieniami:

Bibliografia

Birkhoff, G. Lattice Theory. 3. wyd., American Mathematical Society, 1967.
Grätzer, G. Lattice Theory: Foundation. Birkhäuser, 2011.
Davey, B.A.; Priestley, H.A. Introduction to Lattices and Order. 2. wyd., Cambridge University Press, 2002.